package leecode

func pathSum(root *TreeNode, targetSum int) (result [][]int) {
	if root == nil {
		return
	}
	sum := root.Val
	var backtracking func(node *TreeNode)
	path := make([]int, 0)
	path = append(path, root.Val)
	backtracking = func(node *TreeNode) {
		if node.Left == nil && node.Right == nil {
			if sum == targetSum {
				temp := make([]int, len(path))
				copy(temp, path)
				result = append(result, temp)
			}
			return
		}
		//左
		if node.Left != nil {
			sum += node.Left.Val
			path = append(path, node.Left.Val)
			backtracking(node.Left)
			sum -= node.Left.Val
			path = path[:len(path)-1]
		}
		//右
		if node.Right != nil {
			sum += node.Right.Val
			path = append(path, node.Right.Val)
			backtracking(node.Right)
			sum -= node.Right.Val
			path = path[:len(path)-1]
		}
	}
	backtracking(root)
	return result
}
